"""
堆排序
现在有n个数，设计算法得到前k大的数
解决思路：
> 排序后切片    O(nlogn)
> LowB三人组    O(kn)
> 取列表前k个元素建立一个小根堆，堆顶是目前第k大的数；
  依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；
  遍历列表所有元素后，倒序弹出堆顶  O(nlogk)
"""

def sift(lyst, low, high):  # 最小堆的向下调整
    i = low
    j = 2 * i + 1
    tmp = lyst[low]
    while j <= high:
        if j+1 <= high and lyst[j+1] < lyst[j]:
            j = j + 1
        if lyst[j] < tmp:   # 左右儿子的最小值与i比较
            lyst[i] = lyst[j]
            i = j
            j = 2 * i + 1
        else:
            break
    lyst[i] = tmp

def heap_sort(lyst):
    # 建堆过程：农村包围城市
    n = len(lyst)
    for i in range((n-2)//2, -1, -1):    # 从最后一个有孩子的父节点开始
        sift(lyst, i, n-1)
    for i in range(n-1, -1, -1):
        lyst[0], lyst[i] = lyst[i], lyst[0]
        sift(lyst, 0, i-1)

def topk(lyst, k):
    li = lyst[0:k]
    for i in range((k-2)//2, -1, -1):
        sift(li, i, k-1)
    # 1.建堆
    for i in range(k, len(lyst)-1):
        if lyst[i] > li[0]:
            li[0] = lyst[i]
            sift(li, 0, k-1)
    # 2.遍历
    for i in range(k-1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i-1)
    # 3.出数
    return li
